from typing import List


class MaxHeap:
    def __init__(self, arr=[]):
        self.arr = arr
        self.n = len(arr)

        for i in range(len(arr) // 2, -1, -1):
            self.adjust(i)

    def adjust(self, loc):
        m = loc

        if 2 * loc + 1 < self.n and self.arr[2 * loc + 1] > self.arr[m]:
            m = 2 * loc + 1

        if 2 * loc + 2 < self.n and self.arr[2 * loc + 2] > self.arr[m]:
            m = 2 * loc + 2

        if m == loc:
            return
        self.arr[loc], self.arr[m] = self.arr[m], self.arr[loc]
        self.adjust(m)

    def adjustUp(self, loc):
        if loc == 0:
            return

        if self.arr[(loc - 1) // 2] < self.arr[loc]:
            m = (loc - 1) // 2
            self.arr[loc], self.arr[m] = self.arr[m], self.arr[loc]
            self.adjustUp(m)

    def push(self, num):
        # print('push')
        self.arr.append(num)
        self.adjustUp(self.n)
        self.n += 1
        # self.test()

    def pop(self):
        # print('pop')
        out = self.arr[0]
        tmp = self.arr.pop()
        self.n -= 1

        if len(self.arr) == 0:
            self.test()

            return out
        self.arr[0] = tmp
        self.adjust(0)
        # self.test()

        return out

    def test(self):
        print(self.arr)

        if self.n > 0 and self.arr[0] != max(self.arr):
            # print(len(self.arr))
            self.arr[12345]


class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        mh = MaxHeap([arr[0]])

        for num in arr[1:]:
            if mh.n < k:
                mh.push(num)
            elif num < mh.arr[0]:
                mh.pop()
                mh.push(num)

            # print(num,mh.n,mh.arr)

        # print(len(mh.arr))
        # print(mh.n)

        return mh.arr


sl = Solution()
arr = [
    29234, 28, 940, -48, 20347, 42, -8047, -38796, -6, -43, 6, 5, 18200, -948,
    7571, 15848, 1122, -30790, -40, 8845, -6520, 16, -52289, 75, -405, 34354,
    2392, -43682, -29, 4565, -7448, 9438, 57834, -15924, 4, 88, -4948, 7508,
    548, 41979, -6, -4, 58, -77, 11378, -25875, -32, 79, -418, -3752, 7880,
    -83, 46, 1, 29425, -8, -62787, -9241, 31213, -7, -412, -901, -6, 81, 750,
    -9469, 819, 9699, 638, -7977, 981, -5057, 6, 5427, 9, -370, 29901, -5249,
    69, 622, 37695, -168, 2, -6, 29949, 23612, 375, -8, 9380, -48, 724, 7548,
    -5252, 43, -9, 542, 294, -84, 57726, -27169, 20651, -66, -869, 24, 169,
    -60, 2637, 0, 97, -9659, -778, 9, -3, -73, 3762, -46, -48006, -67, 608, 20,
    0, -492, 61, 13, 3378, -34870, -20, 114, 13987, 4, 2491, 7, 803, -7384,
    366, 17, 538, -660, -23065, 4, 281, 17, 1735, -8, 34264, 141, -12174, -60,
    -8, -4, 4, -1952, 852, -913, 4, 5020, -446, 41532, -93, 46611, 861, -57,
    31248, 6658, 14250, -934, -5887, -379, 42837, 17986, -844, 686, -5581,
    -6966, 9, -16, 26509, -58932, -916, -6036, 32311, -2, 82, -2, 13283,
    -54650, -3, 9, 3, 38317, -34124, 325, 42349, -8408, -22374, -4, -11, 41921,
    -9356, -5, -3, 8, -624, -52273, -36963, -51285, 5946, 39109, 60627, 751,
    -1593, -7588, 1, -6, -5455, -6513, -2908, -248, 12, 476, -61521, -5225,
    -5483, -895, -72, 2497, 36, 13, -259, 6, -1, 13333, -37648, -1, -4, 71, 96,
    -3028, -798, -2903, -2, 56031, -76, -9793, 9925, -32091, 0, -157, 878, -75,
    823, 3430, -299, 51289, 64686, -5426, -6010, -4512, -713, 53, 59736,
    -55493, 19793, 31365, -50, 6407, -27, 21, 21277, 82, -47196, 6368, 4, -3,
    -375, -1, 242, 888, -12688, 1, 424, 642, 131, -61, -22, -108, 5, -27765,
    -9, -37441, -324, 18724, 43326, 40, 5497, -651, -27153, 61, -170, 46404,
    -30193, 29, 19301, -6496, 263, -8204, 9, 402, 10635, -2657, -6, -479, 8569,
    7, 0, -19147, -27753, 5016, -8, 24, -532, 773, -38499, -6877, 551, 44012,
    5, -21285, 875, -11419, 59, 4732, -52, -96, -7054, -65, 9880, -41999, 29,
    7793, 1, -7177, 29, -119, -4741, 8, 3603, 778, 8, 58, -24212, 15, 55260,
    -60, 9, 2469, 1736, 0, -5555, 86, -56368, -51713, -62628, -20985, -4288,
    468, -680, 89, 444, -361, -493, 40655, -26, 35, 45229, 38129, -19122, 4208,
    2, -6, 3252, 45805, 58, -307, 867, 48, -603, -8, 69, 919, -34420, 733, 5,
    90, 6, -74, -3, -18778, 1, -34775, 50211, 138, 42955, -5484, -5456, 2,
    -11040, 7, -9825, 22, -6, 32, -35218, -39, 59620, -153, 9, -46, 9, 35971,
    -9384, -5389, -1804, -6, -59082, -86, -9, 7406, 48124, 9, -5, 868, 696,
    -2372, 612, -51, 28, -17070, -987, -449, 34149, -3, 5650, -2, 2364, -664,
    36, -839, -8, 79, -30673, 980, -7, 0, 3683, -56010, 35, 9, 43176, 569, -5,
    -729, 91, 7, 42, 3, 63548, 8, -66, -72, 501, 86, -97, -37934, -123, -1,
    -32518, 6, -62705, -46937, -54596, 40878, -791, -60131, -45370, 417, 59635,
    -8496, -75, -99, 812, 8165, 5, 869, 487, -446, 61573, -20, 1, -519, 13,
    -59141, -400, -9624, -3, 87, 25778, -60, 89, -861, -4, 3799, -5, -32406,
    718, -52324, -53428, -1185, 7, -24455, 7106, 1, 47, 3, 6, 0, -8, 903,
    10576, -4278, -695, 33, 1979, -55911, -5, 2961, 22127, 37, 48, 5, 7, -15,
    159, 4280, 25, 16, -3, -639, -14, -51, -565, -2464, -72, 87, -19, -645,
    -872, -8476, -423, 9376, -230, 48, 56622, 68, 30, 26638, -760, -45, -179,
    -80, 2760, 170, 9758, -3, -619, -51093, 769, 58, 728, -3, -676, 56, 47, 22,
    -57, 30, -4, -9384, -75, 65, 310, 27, -2, 288, 184, -21, -87, 83, -50,
    12372, -611, 72, -30895, 30824, -6537, 4, 119, -331, -954, -599, 4, 149,
    8055, -465, -28435, 51, -196, 634, 8360, 4979, 20, -8, -41736, 62107,
    -56414, -1216, -57478, -85, -5, -4891, -7, 30, -1738, 32098, -42139, 9,
    -13892, 75, 8633, 368, 52, -89, -80, -8503, -76, 65224, 789, 5, 7226,
    -38807, -38990, 16, -1, -66, -70, 48900, -22708, -7385, 894, 27909, 8, 8,
    -6226, 863, -1881, -519, 619, -61, -58558, -19761, 54, 22681, 68, -1, 7,
    -673, 507, -8980, -858, -35360, 278, -3944, 68, -18086, -943, -51647,
    -30958, -596, 24295, 78, 26077, 734, 529, -468, -49012, 46, -506, -11, 718,
    -18, -4338, 6, -195, 24, -247, -6333, 34, 78, -25, 44217, -3192, -62018,
    18984, 897, -40, 42028, -2, 19356, 825, -858, -6, -8, 40, 4, 939, 1, 6437,
    -9564, -246, -763, -7740, 662, 18, 40, -95, 8221, 2, -6, 3175, -524, 58987,
    39784, 33858, 220, 6, 5, 46, -1438, -9, 7, -78, -45710, -76, -6197, 1,
    -50038, -1, 3, 15734, 38300, -4, -14051, -29544, 9, -735, -4586, -893,
    9749, 626, -8463, 48660, -622, -7527, 49, -2, -5, -908, 23, -1622, -6336,
    11, 737, 5641, 842, 36308, -5, -9, 32527, 31, 17623, -8, 30, 37, -33126,
    729, 691, -9, 0, -28503, 8151, 37, -7791, 623, 38, 5, 6273, 42, 34997,
    -1030, -368, -26, -6, 11592, 73, -818, -76, 3, 2899, -6873, 7911, -3318,
    -17, 8045, -86, -7918, 64387, 901, -56805, 8, -565, 4, -6, 7, -35648, 75,
    -2013, 15507, 7, 725, 887, 1, -30100, -192, -33433, -90, -26378, 25248,
    -49, -31152, -10314, 994, 40, -4, 27
]
k = 834
k = 10

out = sl.smallestK(arr, k)
print(out[:10])
out = sorted(out)
expect = sorted(arr)[:k]

print(len(arr))
print(len(out))
print(len(expect))

print(out[-10:])
print(expect[-10:])

for i in range(len(expect)):
    if expect[i] != out[i]:
        print(i, expect[i], out[i])
